package 简单.栈;

import java.util.*;

/**
 * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
 * <p>
 * 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
 * <p>
 * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-greater-element-i
 */
public class 下一个更大元素I_496 {

    public static void main(String[] args) {

    }

    /**
     * 暴力
     * 先找出nums1某一个元素x在nums2的位置
     * 然后找出第一个比x大的元素
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        for (int num1 : nums1) {
            Integer temp = null;
            boolean flag = false;
            for (int num2 : nums2) {
                if (num1 == num2) {
                    temp = num2;
                }
                if (temp != null) {
                    if (num2 > temp) {
                        temp = num2;
                        flag = true;
                        break;
                    }
                }
            }
            if (flag) {
                list.add(temp);
            } else {
                list.add(-1);
            }
        }
        int[] nums = new int[nums1.length];
        if (list.size() > 0) {
            int index = 0;
            for (Integer num : list) {
                nums[index++] = num;
            }
        }
        return nums;
    }

    /**
     * 栈+哈希表
     * 1，使用栈来判断每个元素右边第一个比它大的元素
     * 2，使用哈希表来存储每个值，和右边第一个比它大的元素，因为题目告诉了是没有重复元素的
     * <p>例子
     * 3 5 9 2 4
     * 4    栈为空，入栈，map(4,-1)，栈  4
     * 2    栈顶为4，2<4，栈顶元素即为结果，map(2,4)，栈 2 4
     * 9    栈顶为2，9>2，2出栈，9>4，4出栈，栈为空，map(9,-1)，栈 9
     * 5    栈顶为9，5<9，5入栈，map(5,9)，栈 5 9
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] efficientNextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        //逆序遍历nums2，如果当前元素，比栈顶元素小，入栈，栈顶元素即为结果
        //如果比栈顶元素大，说明，当前元素左边的元素的结果值，只有可能是当前元素或者当前元素左边的值
        //如果栈为空，说明右边没有比当前元素大的元素
        for (int i = nums2.length - 1; i >= 0; i--) {
            int cur = nums2[i];
            //将栈顶元素比当前元素小的出栈
            while (!stack.isEmpty() && cur >= stack.peek()) {
                stack.pop();
            }
            //栈为空，说明右边没有大的元素，返回-1
            map.put(cur, stack.isEmpty() ? -1 : stack.peek());
            stack.push(cur);
        }
        //直接改变nums1数组
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = map.get(nums1[i]);
        }
        return nums1;
    }

}
